前言

今天下班買到飲料心滿意足，今日的挑戰是medium，perfect！題目在這邊：978. Longest Turbulent Subarray；簡單來說，就是要找到vector中相鄰元素差值是相反的連續最長數列。廢話不多說直接開始解題。

想法

這個題目乍看下去，就覺得可以用遍歷一次O(n)解決，可以很greedy的來完成。畢竟，其實題目的本質就跟找什麼最常連續遞增數列差不多，直接一路檢查下去，如果斷了就重新計算就好啦！然後同步一直更新目前最長數列的值。
不過看到這個題目類型的時候，也有隱隱約約的感覺可能也有一路是想用DP解法，看了一下題目下面的tag果然有dynamic programmingXD 但這題的題目很單純，殺雞焉用牛刀，可以greedy就直接下去就好啦！不過也可以思考一下DP怎麼解，訓練一下DP敏銳度，畢竟當題目複雜起來，DP還是很好用的。
不過這題我一開始也有小小地掉個坑，例如，我本來是這樣寫的：

class Solution {
public:
    int maxTurbulenceSize(vector<int>& arr) {
        // greedy to find the current maxima
        if(arr.size()<=2){
            return arr.size();
        }
        int curL=2;
        int ans=1;
        int curS=bool(arr[1]>arr[0]);
        for(int i=2;i<arr.size();++i){// from the second one to compute the difference
            if (curS != arr[i]>arr[i-1]){
                ++curL;
            }else
            {
                curL=2;
            }
            curS = (arr[i]>arr[i-1]);
            ans = max(ans, curL);    
        }
        return ans;
    }
};

看一下，發現問題了嗎？
沒錯，忘記考慮相鄰元素是相等的情況了！本來很直覺地想說，看題目給的example，只有一個的話答案就是1，或兩個就是2，但像[9,9]的情況答案是1才對！因為相鄰兩者=的情況就不屬於有方向的情況。
考慮到這點，做了一些修改，可能也有更精簡的寫法，就可以再看著改囉。

class Solution {
public:
    int maxTurbulenceSize(vector<int>& arr) {
        // greedy to find the current maxima
        if(arr.size()==1){
            return 1;
        }
        if(arr.size()==2){
            if(arr[1]!=arr[0]){
                return 2;
            }
        }
        int curL=1;
        if(arr[1]!=arr[0]){
            curL=2;
        }
        int ans=1;
        int curS=bool(arr[1]>arr[0]);
        for(int i=2;i<arr.size();++i){// from the second one to compute the difference
            if (curS != arr[i]>arr[i-1] && arr[i]!=arr[i-1]){
                ++curL;
            }else if(arr[i]!=arr[i-1])// same way
            {
                curL=2;
            }else// consider equal condition
            {
                curL=1;
            }
            curS = (arr[i]>arr[i-1]);
            ans = max(ans, curL);    
        }
        return ans;
    }
};

時間複雜度是O(n)複雜度不用懷疑，至於空間則是O(1)，大概只需要存curL、ans、curS這幾個變數而已，不會因為題目的數列長度不同而增加。
最後再來講一下前面提到的DP作法，本來打完跳到別的頁面沒存到檔再來重打一次= =
經典DP就是把問題縮小到只考慮當下狀況+前面狀況就好，所以可以用一個n長度的vector來存必定包含該格的最長數列，更新方法就是先填入第0格是1，第1格如果第零個元素跟第一個元素不同就是2，跟第一個元素相同相同就是1，並記錄方向，接下來只要考慮當下元素的方向是否跟前者不同且元素不可相等，不同該格就=前一格+1，相同該格就=2，元素相等則是1，最後再去找裡面的最大值；上面的作法時間複雜度一樣是O(n)，但空間複雜度也是O(n)，當然空間複雜度也可以優化成只存previousState就也是O(1)，不過就是比較有系統化的解法~

結語

今天文章內容應該有比較充實吧！重打了一次Q